package com.dhnsoft.代码随想录.链表;

import java.util.List;

/**
 * ClassName: d02_707_设计链表
 * Package: com.dhnsoft.代码随想录.链表
 * Description:
 *
 * @Author dhn
 * @Create 2024/3/7 16:43
 * @Version 1.0
 */
public class d02_707_设计链表 {

}
class ListNode {

    int val;
    ListNode next;
//    ListNode prev;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
}
class MyLinkedList {

    ListNode head;
    int size;

    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);
    }

    public int get(int index) {
        if(index<0||index>=size){
            return -1;
        }
        ListNode temp = head;
        for (int i = 0 ;i<=index;i++){
            temp = temp.next;
        }
        return temp.val;
    }

    public void addAtHead(int val) {
        addAtIndex(0,val);
    }

    public void addAtTail(int val) {
        addAtIndex(size,val);
    }

    // 在第 index 个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
    // 如果 index 等于链表的长度，则说明是新插入的节点为链表的尾结点
    // 如果 index 大于链表的长度，则返回空
    public void addAtIndex(int index, int val) {
        if(index>size){
            return;
        }
        if(index<0){
            index = 0;
        }
        size++;
        ListNode pred = head;
        for (int i=0;i<index;i++){
            pred = pred.next;
        }
        ListNode toAdd = new ListNode(val);
        toAdd.next = pred.next;
        pred.next = toAdd;
    }

    public void deleteAtIndex(int index) {
        if(index<0 || index>=size){
            return;
        }
        size--;
        //如果要删除的在头节点，则直接head后移
        if(index == 0){
            head = head.next;
            return;
        }
        ListNode temp = head;
        for (int i=0;i<index;i++){
            temp = temp.next;
        }
        temp.next = temp.next.next;


    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */